package com.dsz.day5.dfs_bfs;
import java.util.*;

public class DFSExample {
    // 图的节点数量
    private static final int NUM_VERTICES = 5;

    // 邻接表表示的图
    private static List<List<Integer>> adjList = new ArrayList<>(NUM_VERTICES);

    public static void main(String[] args) {
        // 初始化邻接表，对应五个节点的邻接表，。创建了5个空的ArrayList
        for (int i = 0; i < NUM_VERTICES; i++) {
            adjList.add(new ArrayList<>());
        }

        // 添加图的边（无向图，所以添加两次）
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 2);
        addEdge(2, 0);
        addEdge(2, 3);
        addEdge(3, 3);
        addEdge(4, 3);

        // 打印DFS遍历结果
        boolean[] visited = new boolean[NUM_VERTICES];
        System.out.println("DFS traversal starting from vertex 2:");
        dfs(2, visited);
    }

    // 添加边到图中
    private static void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src); // 因为是无向图，所以添加双向边
    }

    // 深度优先搜索算法
    //visited是一个布尔数组，用于记录每个节点是否被访问过
    private static void dfs(int vertex, boolean[] visited) {
        // 标记当前节点为已访问
        visited[vertex] = true;
        System.out.print(vertex + " ");

        // 递归访问所有未访问的相邻节点-------------------------------------------------
        //for语句是遍历当前节点的邻接节点，adjList.get(vertex)返回的是一个List，包含当前节点的所有邻接节点
        for (int neighbor : adjList.get(vertex)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }
}